package qjc.h_二叉树;

import com.二叉树.练习题.TreeNode;

public class h15_二叉树中的最大路径和 {
    /**
     * 解题思路：
     * 本题要求找到二叉树中路径和的最大值。路径可以经过任意节点，且必须是连续的（父子相连）。
     * <p>
     * 核心思想：递归 + 分治 + 全局最大值维护
     * <p>
     * 1. 定义递归函数 maxGain(node) 表示以当前节点为起点，向下延伸所能获得的最大路径和（至少包含该节点）；
     * 2. 对于每个节点，计算经过它的“最大路径和”：
     * - 路径可以来自左子树 + 当前节点 + 右子树（此路径不能向上延伸，但可用于更新全局最大值）；
     * - 返回值只能是当前节点 + 左或右子树中的较大者（因为路径不能分叉，只能选一条向上传）；
     * 3. 使用全局变量 maxSum 记录遍历过程中出现的最大路径和；
     * 4. 递归过程中，每访问一个节点都尝试用其“完整路径”（左右+自身）更新 maxSum；
     * 5. 最终 maxSum 即为答案。
     * <p>
     * 关键点：
     * - 路径可以不经过根，也不需要到达叶子；
     * - 负增益的子路径用 Math.max(..., 0) 剪枝，避免拖累总和；
     * - 递归返回的是单向最大增益，而更新的是双向完整路径。
     * <p>
     * 时间复杂度 O(n)，空间复杂度 O(h)（h 为树高，递归栈深度）。
     *
     * @param root
     * @return
     */
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftGain = Math.max(maxGain(root.left), 0);
        int rightGain = Math.max(maxGain(root.right), 0);
        int newGain = root.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, newGain);
        return root.val + Math.max(leftGain, rightGain);
    }
}
